package fun.ticsmyc.question;

import fun.ticsmyc.tools.ArrayTools;

/**
 * 五个好朋友算法
 * 最大K个
 * @author Ticsmyc
 * @date 2020-04-12 17:28
 */
public class BFPRT {

    //最小的k个
    public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
        if (k < 1 || k > arr.length) {
            return arr;
        }

        //先拿到第k个
        int minKth = getMinKthByBFPRT(arr, k);

        //创建结果集
        int[] res = new int[k];
        int index = 0;

        //小于minKth的数
        for (int i = 0; i != arr.length; i++) {
            if (arr[i] < minKth) {
                res[index++] = arr[i];
            }
        }
        //前面的数加起来不够k个，就加上等于minKth的数
        for (; index != res.length; index++) {
            res[index] = minKth;
        }
        return res;
    }

    /**
     第k个
     */
    public static int getMinKthByBFPRT(int[] arr, int K) {
        if(K<=0 || K>=arr.length){
            return Integer.MAX_VALUE;
        }
        return select(arr, 0, arr.length - 1, K - 1);
    }

    /**
     * 使用优化的partation方法寻找【排序后下标为k的值】
     * @param arr
     * @param begin
     * @param end
     * @param k
     * @return
     */
    public static int select(int[] arr, int begin,int end,int k){
        if(begin ==end ){
            return arr[begin];
        }
        //寻找参考值
        int pivot = medianOfMedians(arr,begin,end);

        int[] res = partation(arr,begin,end,pivot);
        if(k < res[0]){
            //左边找
            return select(arr,begin,res[0]-1,k);
        }else if(k > res[1]){
            //右边找
            return select(arr,res[1]+1,end,k);
        }else{
            return pivot;
        }
    }

    /**
     * 寻找合适的pivot
     * 【BFPRT的核心】
     * @param arr
     * @param begin
     * @param end
     * @return
     */
    public static int medianOfMedians(int[] arr ,int begin ,int end){
        int length  = end-begin +1;
        int offset = length %5==0? 0:1;
        int[] mArr = new int[length /5 + offset];
        for (int i = 0; i < mArr.length; i++) {
            int left = begin + i*5;
            int right = Math.min(left +4,end);
            mArr[i] = getMedian(arr,left,right);
        }
        return select(mArr,0,mArr.length-1,mArr.length/2);
    }


    /**
     * 使用pivot作为参考值进行划分 小数在左大数在右
     * 返回值是中间那段等于参考值的子串的起始位置和终止位置
     * @param arr
     * @param head
     * @param tail
     * @param pivot
     * @return
     */
    public static int[] partation(int[] arr, int head, int tail, int pivot){
        int left =head-1;
        int right =tail +1;
        int cur =head;
        while(cur < right){
            if(arr[cur] < pivot){
                ArrayTools.swap(arr,cur++,++left);
            }else if(arr[cur] > pivot){
                ArrayTools.swap(arr,cur,--right);
            }else{
                cur++;
            }
        }
        return new int[]{left+1,right-1};
    }

    /**
     * 对begin到end这段排序 取中位数  (使用插入排序)
     * @param arr
     * @param begin
     * @param end
     * @return
     */
    public static int getMedian(int[] arr,int begin,int end){
        //插入排序
        for(int i=begin+1 ;i<=end; ++i){
            int temp = arr[i];
            int j=i-1;
            while(j>=0 && arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=temp;
        }
        return arr[ (begin+end)/2+(begin+end)%2];

    }

    public static void main(String[] args) {
        int[] arr = { 6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9 };
        // sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }
        System.out.println(getMinKthByBFPRT(arr,20));
        ArrayTools.printArray(getMinKNumsByBFPRT(arr,20));
    }

}
